// Growth rate calculator.
// Memory-efficient calculator of strongly-connected components of a DFA.

#ifndef GRATE_SCC_BUILDER_H
#define GRATE_SCC_BUILDER_H

namespace growth_rate {

class DFAInterface;

class SccPartition {
 public:
  explicit SccPartition(size_t dfa_size)
      : scc_(dfa_size), scc_number_(0) {
    scc_.clear();
  }
  SccPartition(int *scc, size_t length)
      : scc_(length), scc_number_(0) {
    for (size_t i = 0; i < length; i++) {
      CHECK_GE(scc[i], 0);
      scc_[i] = scc[i];
      scc_number_ = Max(scc_number_, scc[i]);
    }
  }
  int scc_for_node(size_t node) const {
    DCHECK_LT(node, scc_.length());
    return scc_[node];
  }
  int length() const { return scc_.length(); }
  int scc_number() const { return scc_number_; }

 private:
  // Array of SCC numbers - i-th element stores the number of SCC for the
  // i-th node, or 0, if this node doesn't lie in any SCC.
  ScopedArray<int> scc_;
  // Number of different scc.
  int scc_number_;
  friend class SccBuilder;
};

class SccBuilder {
 public:
  static SccPartition *build_scc_naive(const DFAInterface *dfa);
};

}  // namespace growth_rate

#endif  // GRATE_SCC_BUILER_H
